#include "graphe.hpp"


graphe * initGraphe (bool verbose ) {
    graphe *g = (graphe*) malloc (sizeof(graphe));

    g->arcs = NULL;
    g->capa_arcs = 0;
    g->nb_arcs = 0;

    g->noeuds = NULL;
    g->capa_noeuds = 0;
    g->nb_noeuds = 0;

    return g;
}
//initiaise un arbre vide

void ajoutNoeud (graphe *g, char * nomNoeud, bool verbose ){
    if (verbose)
    {
        cout << "=========================" << endl;
        cout << "entrée dans ajout Noeud" << endl << "nom du noeud à ajouter : " << nomNoeud << endl << "etat du graphe : " << endl;
        afficherGraphe(g);
    }

    Noeud *ajout = rechercheNoeud(g, nomNoeud, verbose);


    if(ajout == NULL) {
        ajout = initNoeud(nomNoeud, verbose);

        agrandirNoeuds(g, verbose);

        g->noeuds[g->nb_noeuds] = ajout;
        g->nb_noeuds++;

    } else {
        cout << "le noeud " << nomNoeud << " est déjà dans le graphe." << endl;
    }

    if (verbose)
    {
        cout << endl << "sortie de ajout Noeud" << endl << "nom du noeud ajouté : " << nomNoeud << endl << "etat du graphe : " << endl;
        afficherGraphe(g);
    }


}

void ajoutNoeud (graphe *g, Noeud *n, bool verbose ) {
    Noeud *ajout = rechercheNoeud(g, n->nom, verbose);

    if(ajout == NULL) {
        agrandirNoeuds(g, verbose);

        g->noeuds[g->nb_noeuds] = n;
        g->nb_noeuds++;

    } else {
        cout << "le noeud " << n->nom << " est déjà dans le graphe." << endl;
    }
}

void agrandirNoeuds (graphe *g, bool verbose) {

    if(verbose) { cout << endl << "Dans agrandirNoeud()" << endl << "nb_noeuds : " << g->nb_noeuds << "/ capa_noeuds : " << g->capa_noeuds << endl;}

    if(g->nb_noeuds == g->capa_noeuds) {
        if(g->capa_noeuds == 0) {
            g->capa_noeuds = 1;
            g->noeuds = (Noeud**) malloc(g->capa_noeuds*sizeof(Noeud*));
        } else {
            g->capa_noeuds *= 2;
            if (verbose) { cout << "nouvelle taille : " << g->capa_noeuds << endl;}

            g->noeuds = (Noeud**) realloc(g->noeuds, sizeof(Noeud*)*g->capa_noeuds);
        }
    }
}

int suppressionNoeud(graphe *g, char * nomNoeud, bool verbose)
{
    return suppressionNoeud(g, rechercheNoeud(g, nomNoeud, verbose), verbose);
}

int suppressionNoeud(graphe *g, Noeud *n, bool verbose)
{
    if (verbose)
        cout << "entrée dans supressionNoeud" << endl;

    int pos = 0; // position du noeud
    while (g->noeuds[pos] != n)
    {
        if(pos == g->nb_noeuds)
        {
            cout << "ce noeud n'est pas dans le graphe" << endl;
            return 1;
        }
        pos ++;
    }

    if (verbose)
    {
        cout << "noeud trouvé" << endl;
        affichageNoeud(n);

    }
    // On supprime les arcs liés au noeud
    if (verbose)
        cout << "suppression des arcs exterieurs" << endl;

    while (n->nb_arc_ext != 0)
    {
        if (verbose)
        {
            cout << "nombre d'arcs restants " << n->nb_arc_ext << endl;
            cout << "\tsuppression du noeud en direction de " << n->arc_inc_ext[n->nb_arc_ext-1]->dst->nom << endl;
        }
        if(suppressionArc(g, n->arc_inc_ext[n->nb_arc_ext-1], verbose))
            return 1;
    }

    if (verbose)
        cout << "suppression des arcs interieurs" << endl;

    while (n->nb_arc_int != 0)
    {
        if (verbose)
        {
            cout << "nombre d'arcs restants " << n->nb_arc_int << endl;
            cout << "\tsuppression du noeud qui viens de " << n->arc_inc_int[n->nb_arc_int-1]->src->nom << endl;
        }

        if(suppressionArc(g, n->arc_inc_int[n->nb_arc_int-1], verbose))
            return 1;
    }

    testamentNoeud(n);
    // décalage des arcs
    if (verbose)
        cout << "noeud supprimé" << endl;
    if(pos < (g->nb_noeuds - 1)) // si le noeud n'était pas le dernier du tableau
    {
        g->noeuds[pos] = g->noeuds[g->nb_noeuds - 1];
        g->noeuds[g->nb_noeuds - 1] = NULL;
        if (verbose)
            cout << "Dernier noeud décalé, nouvelle position de " << g->noeuds[pos]->nom << " : " << pos << endl;
    }
    if(g->nb_noeuds < g->capa_noeuds/2)
    {
        g->capa_noeuds /= 2;
        g->noeuds = (Noeud**) realloc(g->noeuds, sizeof(Noeud*)*g->capa_noeuds);
        if (verbose)
            cout << "tableau de noeuds redimensioné" << endl;
    }
    g->nb_noeuds --;
    return 0;
}

Noeud * rechercheNoeud(graphe *g, char * rech, bool verbose)
{
    if (verbose) {cout << "\tentrée dans rechercheNoeud, noeud recherché : " << rech << endl;}

    for(int i = 0; i < g->nb_noeuds; i++) {

        if(strcmp(rech, g->noeuds[i]->nom) == 0) {
            return g->noeuds[i];
        }
    }

    return NULL;
}


void ajoutArc (graphe *g, char * src, char * dst, int valeur, bool verbose ) {

    Noeud* n_src = rechercheNoeud(g, src);
    Noeud* n_dst = rechercheNoeud(g, dst);

    if((n_src!=NULL)&&(n_dst!=NULL)){

        Arc *ajout = rechercheArc(g, src, dst, verbose);

        if(ajout == NULL) {

            ajout = initArc(n_src, n_dst, valeur, verbose);

            agrandirArcs(g, verbose);

            g->arcs[g->nb_arcs] = ajout;
            g->nb_arcs++;

            ajouteArcExt(n_src, ajout, verbose);
            ajouteArcInt(n_dst, ajout, verbose);

        } else {
            if (verbose)
                cout << "l'Arc " << src << "->" << dst << " est déjà dans le graphe." << endl;
            ajout->valeur = valeur;
        }

    } else {
        if(n_src == NULL)
            cout << "le noeud " << src << " n'existe pas " << endl;
        if(n_dst == NULL)
            cout << "le noeud " << dst << " n'existe pas " << endl;
    }
}

void ajoutArc (graphe *g, Arc *a, bool verbose ) {
    Arc *ajout = rechercheArc(g, a->src->nom, a->dst->nom, verbose);

    if(ajout == NULL) {
        ajout = a;

        agrandirArcs(g, verbose);

        g->arcs[g->nb_arcs] = ajout;
        g->nb_arcs++;

    } else {
        //cout << "l'Arc " << a->src->nom << "->" << a->dst->nom << " est déjà dans le graphe." << endl;
        ajout->valeur = a->valeur;
    }
}

void agrandirArcs (graphe *g, bool verbose ) {
    if(verbose) { cout << endl << "Dans agrandirArc()" << endl << "nb_arcs : " << g->nb_arcs << "/ capa_arcs : " << g->capa_arcs << endl;}

    if(g->nb_arcs == g->capa_arcs) {
        if(g->capa_arcs == 0) {
            g->capa_arcs = 1;
            g->arcs = (Arc**) malloc(g->capa_arcs*sizeof(Arc*));
        } else {
            g->capa_arcs *= 2;
            g->arcs = (Arc**) realloc(g->arcs, sizeof(Arc*)*g->capa_arcs);
        }
    }
}

int suppressionArc(graphe *g, char * src, char * dst, bool verbose)
{
    return(suppressionArc(g, rechercheArc(g, src, dst, verbose)));
}


int suppressionArc(graphe *g, Arc *a, bool verbose)
{
    int pos = 0;
    while (g->arcs[pos] != a)
    {
        if(pos == g->nb_arcs)
        {
            cout << "l'arc n'est pas dans le graphe" << endl;
            return 1;
        }
        pos ++;
    }

    if (verbose)
    {
        cout << " -------------- " << endl;
        affichageArc(a);
    }

    decrocherArcExt(a->src, a, verbose);
    decrocherArcInt(a->dst, a, verbose);

    testamentArc(a);
    if (pos < (g->nb_arcs -1))
    {
        g->arcs[pos] = g->arcs[g->nb_arcs - 1];
        g->arcs[g->nb_arcs - 1] = NULL;
        if (verbose)
            cout << "Dernier arc décalé à la position " << pos << endl;
    }
    if(g->nb_arcs < g->capa_arcs/2)
    {
        g->capa_arcs /= 2;
        g->arcs = (Arc**) realloc(g->arcs, sizeof(Arc*)*g->capa_arcs);
        if (verbose)
            cout << "tableau de arcs redimensioné" << endl;
    }
    g->nb_arcs --;
    return 0;
}

Arc * rechercheArc(graphe *g, char * src, char * dst, bool verbose ) {

    for(int i = 0; i < g->nb_arcs; i++) {
        if(strcmp(src, g->arcs[i]->src->nom) == 0) {
            if(strcmp(dst, g->arcs[i]->dst->nom) == 0) {
                return g->arcs[i];
            }
        }
    }

    return NULL;
}

void afficherGraphe (graphe *g, bool verbose) {

    if(verbose) { cout << "Entrée dans afficherGraphe()" << endl;}

    cout << endl << "Affichage du graphe" << endl << endl;;

    //cout << "\tNoeuds : " << endl;
    for(int i =0; i < g->nb_noeuds; i++)
        affichageNoeud(g->noeuds[i]);
/*
    cout << endl << "\tArcs : " << endl;
    for(int i =0; i < g->nb_arcs; i++)
        affichageArc(g->arcs[i]); */
}

void testamentGraphe (graphe *g)
{
    for(int i = 0; i<g->nb_noeuds; i++)
    {
        testamentNoeud(g->noeuds[i]);
    }

    for (int i = 0; i<g->nb_arcs; i++)
    {
        testamentArc(g->arcs[i]);
    }

    g->capa_noeuds = 0;
    g->nb_noeuds = 0;
    g->capa_arcs = 0;
    g->nb_arcs = 0;

    free(g->noeuds);
    free(g->arcs);
    free(g);
}
